1. Field of the Invention
The present invention relates generally to a road map information readout apparatus, a recording medium and a transmitting method, and more particularly, to a road map information readout apparatus, a recording medium and a transmitting method which are used for applications such as the display of an arbitrary position of a map, a detection of the current position, or a calculation of a route from the current position to a determination.
2. Description of the Related Art
Data including various types of information relating to roads used for a vehicle navigation or the like is generally referred to as vector map data. The vector map data is composed of data representing nodes, links, connection information, a link shape, and attribute information.
The node data is data mainly representing an intersection of roads. The link data is data representing a road connecting nodes. The link data is data having vector information. A road map is represented by a set of links. Therefore, such a map is referred to as a vector map. The connection information data is data representing a connection between nodes and links. The link shape data is data for complementing, when the map is insufficiently represented by only the nodes, the links and the connection information thereof, the map representation. For example, roads in mountainous and coastal areas may, in some cases, be bent. In this case, the bent shape of the road cannot be sufficiently represented by only one link data corresponding to the road. Therefore, in order to suitably represent the bent shape of the road, the bent shape is complemented as the link shape data. The attribute information data includes node attribute data relating to the nodes and link attribute data relating to the links. The node attribute data is data representing the name of an intersection, the presence or absence of a signal, and the like. The link attribute data is data representing the name of a road, the type of road, for example, a national road or a prefectural road, the number of lanes, and the presence or absence of a median strip.
A conventional map information display device using a vector map composed of the above-mentioned various types of data will be described.
Description is now made of the format of the vector map data used in the conventional map information display device. One example of the format of the conventional vector map data is a format disclosed in a text of "Trend to Put High-Accuracy Route Guide System to Practical Use" (hereinafter referred to as a first document) in a seminar sponsored by the Japan Industry Engineering Center. In the first document, a method of representing links and a compression of connection information are described in relation to the format of data.
FIG. 18 is a diagram showing a recording method for representing a connection of roads which is described in the first document. In the recording method described in the first document, identification data of a node to be connected, which is referred to as an index, and data representing the distance to a node at its destination of connection or time required for movement, which is referred to as a cost, are recorded for each node in order to record a connection between nodes. FIG. 18(a) illustrates an example of a cost table composed of arbitrary nodes. FIG. 18(a) illustrates a state where in a road network composed of eight nodes, one of the nodes in the road network is connected to the other four nodes (corresponding to indexes 2, 3, 4 and 7). A cost between the one node and the other node is represented by a hexadecimal number (for example, "2" in the index 2). Costs corresponding to nodes to which no connection is made are represented by setting a hexadecimal number "FFFF" (corresponding to indexes 1, 5, 6 and 8).
FIG. 18(b) illustrates an example of a recording system containing respective connection information shown in the cost table in FIG. 18(a) (hereinafter referred to as an example of the recording system 1). The example of the recording system 1 has as its object not only to simply record costs corresponding to the eight nodes but also to reduce the amount of information to be recorded. In the example of the recording system 1, when the nodes having the same cost are continuous, only information relating to the final node out of the continuous nodes is recorded, and information relating to the preceding nodes having the same cost are all deleted. Specifically, in the example of the recording system 1, both the costs corresponding to the indexes 3 and 4 are "7". Therefore, after the cost relating to the index 2 is recorded, the cost relating to the index 4 is recorded. Further, the costs corresponding to the indexes 5 and 6 are the same. Therefore, after the cost relating to the index 4 is recorded, the cost relating to the index 6 is recorded. Consequently, the number of nodes to be recorded is "6", exclusive of the indexes 3 and 5, with respect to the respective connection information shown in the cost table in FIG. 18(a). Further, the data capacity of the connection information of the nodes is the number of rows in the example of the recording system 1, i.e., "14".
In the example of the recording system 1, however, the connection information are also recorded with respect to the nodes to which no connection is made, thereby the recording efficiency is low. Therefore, in the first document, a recording system shown in FIG. 18(c) (hereinafter referred to as an example of the recording system 2) is employed as another recording system of connection information. In the example of the recording system 2, indexes and costs are recorded only with respect to nodes to which connection is made. Specifically, as shown in the example of the recording system 2, the connection information are recorded only with respect to indexes 2, 3, 4 and 7 in which costs exist.
As described in the foregoing, the amount of information to be recorded of the connection information is basically proportional to the square of the number of nodes in the example of the recording system 1, while the amount of information to be recorded can be reduced to the total number of nodes times the number of nodes which are connected to each of the nodes. In many cases, map data which is divided for each arbitrary region is generally used for vector map data. However, when the map data is divided for each region as described above, the number of nodes in the region is normally several hundred. On the other hand, the number of nodes connected to each of the nodes is three to four on average. This shows that in the example of the recording system 2, the capacity of map information can be significantly reduced, that is, compressed, as compared with that in the example of the recording system 1. The reduction of the connection information is hereinafter referred to as compression of connection information in the present specification.
The connection of roads can be basically represented by only the above-mentioned connection information. In practice, however a method of grouping links having the same attribute and recording a connection of the links has been also generally carried out. A method of representing the connection of links which is described in the first document will be described.
A method of representing the connection of links which is described in the first document is a method of not respectively recording the same attribute for each link, but grouping the links having the same attribute as one road, which can be drawn with one stroke of the brush, and recording one attribute for the grouped roads, when there exist a plurality of links having the same attribute. By this method, recording of one attribute is sufficient by grouping, though a plurality of attributes which are the same are recorded, thereby the recording efficiency is improved. This method is specifically employed for cases such as a case where it is desired to represent only country roads on a map.
FIG. 19 is a diagram showing the difference of a method of representing connection information of links depending on the presence or absence of such a grouping process. In FIG. 19, L0 to L3 denotes links. N0b to N3a and N0b-1a to N2b-3a denote the identification codes of nodes. C1 and C2 denote the costs of the links. Further, C01 to C32 denote data representing the connection states of each node (for example, the node number of a destination of connection, offset information, etc.).
FIG. 19(a) illustrates a method of representing a unit of links which are not grouped. The method of representing a unit of links requires all the costs of the links as well as connection information of nodes at both ends of each of the links in order to connect the links which individually exist. On the other hand, FIG. 19(b) illustrates a method of representing a row of links which are grouped. The method of representing a row of links is a method of recording links in relation to link information in the connection order of the links. In a method of representing a row of links, therefore, it is possible to omit not only the above-mentioned attribute information but also the connection information between the links, as compared with a method of representing a unit of links. Such a grouping of the connection information shall be hereinafter referred to as compression of road information in the present specification.
On the other hand, as the conventional map information display device, a device is disclosed in "Japanese Patent Laid-Open No. 7-37067" (hereinafter referred to as a second document), for example. FIG. 20 is a block diagram showing the construction of the map information display device described in the second document.
Referring to FIG. 20, the conventional map information display device will be described.
In FIG. 20, the map information display device described in the second document comprises vector map data 2001, data conversion portion 2002, first storage portion 2003, second storage portion 2008, position input portion 2007, image processing portion 2004, a frame memory 2005, and display portion 2006.
The capacity of the vector map data 2001 is reduced in accordance with a predetermined thinning method by the data conversion portion 2002. The predetermined thinning method is a method of thinning vector data for representing the shape of a road, that is, link shape data. In the map information display device described in the second document, processing for judging redundant points (end points of vectors) which are hardly affected at the time of displaying a road and thinning the points is performed by utilizing the fact that the shape of the road is represented as a set of line segments (vectors) upon being linearly approximated. The vector map data 2001 whose capacity is reduced is vector map data after data conversion (hereinafter referred to as conversion data), and is stored in the first storage portion 2003 (a medium such as a hard disk). On the other hand, the second storage portion 2008, constituted by a memory which can be accessed at high speed, and stores a required part of the conversion data stored in the first storage portion 2003. The second storage portion 2008 is constituted by a memory which can be accessed at a higher speed, although smaller in capacity, as compared with the first storage portion 2003. Consequently, the image processing portion 2004 can access map data stored in the second storage portion 2008 at high speeds in accordance with designation of a user through the position input portion 2007 (designation of a map which desires to be displayed), drawing the map data on the frame memory 2005, and display the map data using the displaying portion 2006.
As described in the foregoing, in the map information display device described in the second document, the vector map data is thinned, and an expensive storage medium such as a memory which can be accessed at a high speed is used, so that more map information can be stored. Therefore, in the map information display device described in the second document, if the capacity of the memory is the same, vector map data in a wider range can be stored. On the contrary, if the same map information is stored, the capacity of the memory may be smaller. Such thinning of the shape of the road shall be hereinafter referred to as compression of the shape of a road in the present specification.
As described in the foregoing, the map information display devices described in the first document and the second document realize compression of the map information by three compression portions: compression of connection information; compression of road information; and compression of a road shape. Consequently, the map information display devices described in the first document and the second document allow for a reduction of the capacity of the map information recording medium, shortening of time required to read out the map, and recording of information, such as sightseeing information, other than the map information on the same medium.
In recent years, various practical map information display devices and vehicle navigation systems have been developed with vector map data which is subjected to the conventional compression techniques of map information being used as a premise. In the above-mentioned conventional map information display devices or the like, a large-capacity recording medium such as a CD-ROM or a hard disk has been employed as a recording medium of map information in the present conditions. However, in the future, radio or wire transmission of the map information, and utilization of the map information in a portable information equipment in which the capacity of a recording medium is largely limited will be considered. Accordingly, the map information must not have a large capacity as in the present conditions but a smaller capacity under these applications. However, the conventional map information display device or the like has the following problems, thereby the problem of the reduction of the capacity cannot be solved.
First, in a method of compression of connection information in the conventional map information display device or the like, connection information of roads are recorded in the same data format with respect to all the roads.
Roads can be mainly divided into main roads and minor streets. The main road is a road which is considered to be utilized by a large number of people, for example, a country road or a highway. The minor street is a road which is considered to be utilized by a small number of people (or to be usable by only particular persons), for example, a life road in a residential street, a farm road or a path through a forest, contrary to the main road. When the roads are divided into main roads and minor streets in the map information display device or the like, the frequency of use of connection information of roads differs between the main roads and the minor streets. Particularly, in route search processing for calculating a route to a desired position in the map information display device or the like, connection information of main roads is required in a wide range. However, connection information of the minor streets is required only in the restricted range in the vicinity of the current position (a starting point) or a destination. In the actual map data, not less than the half of all the roads may be minor streets in the detailed map of an urban area, for example, in many cases.
However, the conventional map information display device or the like stores the connection information of the roads in the same data format with respect to all the roads irrespective of the above-mentioned contents. Therefore, almost all the connection information is occupied by the connection information of the minor streets low in frequency of use. That is, the problem that the capacity of the map information is large still exists.
Second, in a method of compression of road information in the conventional map information display device or the like, roads cannot be sufficiently grouped.
The compression of road information is for grouping a row of links which are of the same road type and can be drawn with one stroke of the brush. However, there are actually many roads which are of the same type but cannot be drawn with one stroke of the brush. For example, in an urban highway (a metropolitan highway, for example), ramps exist with relatively small spacing. Ramps are an entrance and an exit connecting a main lane of the highway and a general road. Accordingly, the main lane of the highway branches for each ramp. Therefore, when the main lane is drawn with one stroke of the brush to form a group, short links which are merged into the general road and branching for each ramp remain without being included in the group. Consequently, the links have the same attribute but are not directly connected to each other, thereby the links, together with their attributes, must be respectively recorded.
Such a phenomenon is frequently seen in main roads in an urban area, for example, a road portion connecting upper and lower lanes, which are separated, of a main road. Therefore, in the conventional map information display device or the like, the fact that links which can be grouped are limited to a set of links which can be drawn with one stroke of the brush causes the problem that the capacity of the map information is large.
Third, in a method of compression of the shape of a road in the conventional map information display device or the like, the representations of a bent road, a gently curved road, a curved road such as an interchange of a toll road present a problem.
In the method of compression of the shape of a road in the conventional map information display device or the like, a shape close to a curve is represented by setting a large number of interpolation points for representing the shape of a road such as a bent road to perform linear approximation between the interpolation points. Consequently, data representing a lot of interpolation points causes the problem that the capacity of the map information is large.
As described in the foregoing, in the prior art, the map information cannot be sufficiently compressed by the above-mentioned remaining three problems. Since the capacity of the map information is still large, therefore, it is still difficult to realize the transmission of the map information, the storage of the map information in a semiconductor memory, and the like.